/**
 * 
 */
package a0;

import java.util.Random;

/**
 * @author totyu
 *
 */
public class LLKxyz {

    private static final int CARD_ROWS = 20;
    private static final int CARD_COLS = 20;
    private static final int EMPTY = 0;
    private static final int CARD_KIND = 20;
    private static final int DATA_LENGTH = 18 * 18 / 2;

    class Point {
        int x;
        int y;
    }

    private int[][] map = new int[CARD_ROWS][CARD_COLS];

    public void setRndMap() {
        for (int i = 0; i < DATA_LENGTH; i++) {
            setRandPic();
        }
    }

    private Random rand() {
        return new Random();
    }

    private void setRandPic() {
        Point p;
        int pic = rand().nextInt(CARD_KIND) + 1;
        p = getRndEmptyBox();
        map[p.x][p.y] = pic;
        p = getRndEmptyBox();
        map[p.x][p.y] = pic;
    }

    private Point getRndEmptyBox() {
        while (true) {
            int x = rand().nextInt(CARD_ROWS - 2) + 1;
            int y = rand().nextInt(CARD_COLS - 2) + 1;
            if (map[x][y] == EMPTY) {
                Point r = new Point();
                r.x = x;
                r.y = y;
                return r;
            }
        }
    }

    public void dumpMap() {
        int i, j;
        System.out.print("xy: ");
        for (i = 0; i < CARD_ROWS; i++) {
            System.out.print(String.format("%02d ", i));
        }
        System.out.print("\n");
        for (i = 0; i < CARD_COLS; i++) {
            System.out.print(String.format("%02d: ", i));
            for (j = 0; j < CARD_ROWS; j++) {
                System.out.print(String.format("%02d ", map[j][i]));
            }
            System.out.print("\n");
        }
    }

    public boolean searchAllMap() {
        int ix, iy;
        boolean noPathLeft = false;
        while (!noPathLeft) {
            noPathLeft = true;
            for (iy = 0; iy < CARD_COLS; iy++) {
                for (ix = 0; ix < CARD_ROWS; ix++) {
                    if (map[ix][iy] != EMPTY) {
                        Point p = new Point();
                        p.x = ix;
                        p.y = iy;
                        if (searchMap(p) && noPathLeft)
                            noPathLeft = false;
                    }
                }
            }
            System.out.print("next loop...\n");
        }
        return true;
    }

    private boolean searchMap(Point p1) {
        int ix, iy;
        boolean inner1 = true;

        int c1 = map[p1.x][p1.y];
        for (iy = p1.y; iy < CARD_COLS; iy++) {
            for (ix = 0; ix < CARD_ROWS; ix++) {
                if (inner1) {
                    ix = p1.x + 1;
                    inner1 = false;
                }
                if (ix < CARD_ROWS && map[ix][iy] == c1) {
                    Point p2 = new Point();
                    p2.x = ix;
                    p2.y = iy;
                    if (havePath(p1, p2)) {
                        dumpMapWithHotPoint(p1, p2);
                        map[p1.x][p1.y] = EMPTY;
                        map[p2.x][p2.y] = EMPTY;
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean havePath(Point p1, Point p2) {
        if (havePathCorner0(p1, p2)) {
            System.out.print(String.format("[%d,%d] to [%d,%d] have a direct path.\n", p1.x, p1.y, p2.x, p2.y));
            return true;
        }
        Point r = havePathCorner1(p1, p2);
        if (r.x != -1) {
            System.out.print(String.format("[%d,%d] to [%d,%d] have a 1 cornor path throught [%d,%d].\n", p1.x, p1.y,
                    p2.x, p2.y, r.x, r.y));
            return true;
        }
        Point[] c = havePathCorner2(p1, p2);
        if (c[0].x != -1) {
            System.out.print(String.format("[%d,%d] to [%d,%d] have a 2 cornor path throught [%d,%d] and [%d,%d].\n",
                    p1.x, p1.y, p2.x, p2.y, c[0].x, c[0].y, c[1].x, c[1].y));
            return true;
        }
        return false;
    }

    private boolean havePathCorner0(Point p1, Point p2) {
        if (p1.x != p2.x && p1.y != p2.y)
            return false;
        int min, max;
        if (p1.x == p2.x) {
            min = p1.y < p2.y ? p1.y : p2.y;
            max = p1.y > p2.y ? p1.y : p2.y;
            for (min++; min < max; min++) {
                if (map[p1.x][min] != EMPTY)
                    return false;
            }
        } else {
            min = p1.x < p2.x ? p1.x : p2.x;
            max = p1.x > p2.x ? p1.x : p2.x;
            for (min++; min < max; min++) {
                if (map[min][p1.y] != EMPTY)
                    return false;
            }
        }
        return true;
    }

    private Point havePathCorner1(Point p1, Point p2) {
        Point nullPoint = new Point();
        nullPoint.x = nullPoint.y = -1;

        if (p1.x == p2.x || p1.y == p2.y)
            return nullPoint;
        Point c1 = new Point(), c2 = new Point();
        c1.x = p1.x;
        c1.y = p2.y;
        c2.x = p2.x;
        c2.y = p1.y;
        if (map[c1.x][c1.y] == EMPTY) {
            boolean b1 = havePathCorner0(p1, c1);
            boolean b2 = havePathCorner0(c1, p2);
            if (b1 && b2)
                return c1;
        }
        if (map[c2.x][c2.y] == EMPTY) {
            boolean b1 = havePathCorner0(p1, c2);
            boolean b2 = havePathCorner0(c2, p2);
            if (b1 && b2)
                return c2;
        }
        return nullPoint;
    }

    private Point[] havePathCorner2(Point p1, Point p2) {
        int i;
        Point[] r = new Point[2];
        r[0] = new Point();
        r[1] = new Point();

        // search right
        for (i = p1.y + 1; i < CARD_COLS; i++) {
            if (map[p1.x][i] == EMPTY) {
                Point c1 = new Point();
                c1.x = p1.x;
                c1.y = i;
                Point d1 = havePathCorner1(c1, p2);
                if (d1.x != -1) {
                    r[0].x = c1.x;
                    r[0].y = c1.y;
                    r[1].x = d1.x;
                    r[1].y = d1.y;
                    return r;
                }
            } else
                break;
        }
        // search left
        for (i = p1.y - 1; i > -1; i--) {
            if (map[p1.x][i] == EMPTY) {
                Point c1 = new Point();
                c1.x = p1.x;
                c1.y = i;
                Point d1 = havePathCorner1(c1, p2);
                if (d1.x != -1) {
                    r[0].x = c1.x;
                    r[0].y = c1.y;
                    r[1].x = d1.x;
                    r[1].y = d1.y;
                    return r;
                }
            } else
                break;
        }
        // search bottom
        for (i = p1.x + 1; i < CARD_ROWS; i++) {
            if (map[i][p1.y] == EMPTY) {
                Point c1 = new Point();
                c1.x = i;
                c1.y = p1.y;
                Point d1 = havePathCorner1(c1, p2);
                if (d1.x != -1) {
                    r[0].x = c1.x;
                    r[0].y = c1.y;
                    r[1].x = d1.x;
                    r[1].y = d1.y;
                    return r;
                }
            } else
                break;
        }
        // search top
        for (i = p1.x - 1; i > -1; i--) {
            if (map[i][p1.y] == EMPTY) {
                Point c1 = new Point();
                c1.x = i;
                c1.y = p1.y;
                Point d1 = havePathCorner1(c1, p2);
                if (d1.x != -1) {
                    r[0].x = c1.x;
                    r[0].y = c1.y;
                    r[1].x = d1.x;
                    r[1].y = d1.y;
                    return r;
                }
            } else
                break;
        }
        r[1].x = r[0].x = r[0].y = r[1].y = -1;
        return r;
    }

    private void dumpMapWithHotPoint(Point c1, Point c2) {
        int x, y;
        System.out.print("xy: ");
        for (x = 0; x < CARD_ROWS; x++) {
            System.out.print(String.format("%02d ", x));
        }
        System.out.print("\n");
        for (y = 0; y < CARD_COLS; y++) {
            System.out.print(String.format("%02d: ", y));
            for (x = 0; x < CARD_ROWS; x++) {
                if ((c1.x == x && c1.y == y) || (c2.x == x && c2.y == y))
                    System.out.print(String.format("\33[1;31m%02d\33[0m ", map[x][y]));
                else
                    System.out.print(String.format("%02d ", map[x][y]));
            }
            System.out.print("\n");
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        LLKxyz llKxyz = new LLKxyz();
        llKxyz.setRndMap();
        llKxyz.dumpMap();
        llKxyz.searchAllMap();
//        System.out.println(llKxyz.rand().nextInt(_width));
//        System.out.print(String.format("\33[1;31m%02d\33[0m ", 1));
    }

}
